import { TreeNode } from '../base/tree-node';

// 450. 删除二叉搜索树中的节点
// 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
// 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

/**
 * 删除二叉搜索树中的节点
 * @param root 二叉搜索树的根节点
 * @param key 要删除的节点值
 * @returns 删除节点后的二叉搜索树的根节点
 */
export function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  // 1. 递归终止条件：节点为空，直接返回null（修复核心错误）
  if (root === null) return null;

  // 2. 找到要删除的节点
  if (root.val === key) {
    // 2.1 叶子节点（左右都空）：直接删除（返回null）
    if (root.left === null && root.right === null) {
      return null;
    }
    // 2.2 只有右子树：用右子树替代当前节点
    if (root.left === null) {
      return root.right;
    }
    // 2.3 只有左子树：用左子树替代当前节点
    if (root.right === null) {
      return root.left;
    }
    // 2.4 左右子树都存在：找右子树的最左节点（后继节点）
    let successor = root.right;
    while (successor.left !== null) {
      successor = successor.left; // 找到右子树最小值节点
    }
    // 将当前节点的左子树接到后继节点的左子树
    successor.left = root.left;
    // 用右子树替代当前节点（完成删除）
    return root.right;
  }

  // 3. 未找到节点：递归遍历左右子树
  if (key < root.val) {
    root.left = deleteNode(root.left, key); // 更新左子树引用
  } else {
    root.right = deleteNode(root.right, key); // 更新右子树引用
  }

  return root;
}
